class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n=s.length();
        int sum=0;
        int len=0x3f3f3f3f;
        int left=0;
        int right=0;
        //找到最小长度
        while(right<n){
            int t=s.charAt(right)-'0';
            if(t==1){
                sum++;
            }
            while(sum==k){
                len=Math.min(len,right-left+1);
                int tt=s.charAt(left)-'0';
                if(tt==1){
                    sum--;
                }
                left++;
            }
            right++;
        }
        if(len==0x3f3f3f3f){
            return new String();
        }
        //根据最小长度找美丽字符串
        left=right=0;
        sum=0;
        int l=len;
        len=0x3f3f3f3f;
        int min=0x3f3f3f3f;
        String ans=s;
        while(right<n){
            int t=s.charAt(right)-'0';
            if(t==1){
                sum++;
            }
            while(sum==k){
                len=Math.min(len,right-left+1);
                if(l==len){
                    String str=s.substring(left,right+1);
                    if(str.length()<ans.length() || str.length()==ans.length() && str.compareTo(ans)<0){
                        ans=str;
                    }
                }
                int tt=s.charAt(left)-'0';
                if(tt==1){
                    sum--;
                }
                left++;
            }
            right++;
        }
        return ans;
    }
}